#include "Solution.h"
#include <stack>
#include <set>
#include <bitset>
#include <iostream>

void Solution::nextPermutation(vector<int>& nums)
{
    if(nums.empty())
        return;
    int len = nums.size();
    int max = 0;
    int i = len-1;

    for(; i > 0; i--)
    {
        if(nums[i] <= nums[i - 1] )
            continue;
        break; 
    }
    if(i > 0)
    {
        for(int j = len -1 ;j >= i ;j--)
        {
            if(nums[j]  > nums[i -1])
            {
                swap(nums[i-1],nums[j]);
                break;
            }
        }
    }
    sort(nums.begin() + i,nums.end());
}

int Solution::longestValidParentheses(string s)
{
    int maxans = 0;
    stack<int> stk;
    stk.push(-1);
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            stk.push(i);
        } else {
            stk.pop();
            if (stk.empty()) {
                stk.push(i);
            } else {
                maxans = max(maxans, i - stk.top());
            }
        }
    }
    return maxans;
}
int Solution::search(vector<int>& nums, int target)
{
    if(nums.empty())
        return -1;
    int len = nums.size();
    int beg = 0;
    int end = len;
    int i = (end - beg )/2 ;
    while(i)
    {
        if(nums[beg+i] == target)
        {
            return i+beg;
        }
        else if((nums[beg+i] > target && nums[beg] > target && nums[beg+i] > nums[beg] )
                || (nums[beg+i] < target && (nums[end -1] >= target || nums[end-1] < nums[beg+i])))
        {
            beg = beg+i + 1;
            i = (end - beg) / 2;
        }
        else
        {
           end = beg+i; 
           i = i / 2;
        }
    }
    if( beg + i < len && nums[beg+i] == target)
        return beg+i;
    return -1;
}
vector<int> Solution::searchRange(vector<int>& nums, int target)
{
    int len = nums.size();
    int i = len;
    int l = 0 ;
    int r = len - 1;
    while( i )
    {
        i = i/2;
        if(l+i+1 < len && nums[l+i] < target )
        {
            l = l+i+1;
            continue;
        }
        if(r - i -1 >= 0 && nums[r-i] > target )
        {
            r = r -i -1 ;
            continue;
        }
        if(l >= 0)
        {
            if(nums[l] < target)
            {
                l = l +  i/2;
            }
            else if(l >= (i/2 + 1))
            {
                l = l - i/2  -1;
            }
        }
        if(r < len)
        {
            if(nums[r] > target)
            {
                r =  r - i/2 ;
            }
            else if(r + i/2 < len)
            {
                r = r + i/2;            
            }
        }
        cout<<"i="<<i<<"\tl="<<l<<"\tr="<<r<<endl;
    }
    if(nums[r] > target)
        r--;
    if(nums[l] < target)
        l++;
    if(l > r)
    {
        l = -1;
        r = -1;
    }
    return {l,r};
}

int Solution::searchInsert(vector<int>& nums, int target)
{
    if(nums.empty() || nums[0] >= target)
        return 0;
    int len = nums.size();
    if(nums[len-1] < target)
        return len;
    int left = 0;
    int right = len - 1;
    while (left < right) 
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}
bool Solution::isValidSudoku(vector<vector<char>>& board)
{
    /*
    for(int i = 0; i < 9;i++)
    {
        unordered_map<int ,int>  col;
        for(int j = 0; j < 9;j++)
        {
            int num = board[i][j] - '0';
            if(num > 0 && num < 10)
            {
                col[num]++;
                if(col[num] > 1)
                    return false;
            }
        }
    }
    for(int i = 0; i < 9;i++)
    {
        unordered_map<int ,int>  row;
        for(int j = 0; j < 9;j++)
        {
            int num = board[j][i] - '0';
            if(num > 0 && num < 10)
            {
                row[num]++;
                if(row[num] > 1)
                    return false;
            }
        }
    }
    
     for(int i = 0; i < 9;i += 3)
    {
        for(int j = 0; j < 9;j += 3)
        {
            unordered_map<int ,int>  row;
            for(int r = i;r < i+3;r++)
            {
                for(int c = j;c < j+3;c++)
                {
                    int num = board[r][c] - '0';
                    if(num > 0 && num < 10)
                    {
                        row[num]++;
                        if(row[num] > 1)
                            return false;
                    }
                }
            }
        }
    }
    */
    int  list[9][9]= {};
    int  col[9][9] ={};
    int  row[9][9] ={};
    for(int i = 0;i < 9; i++)
    {
        for(int j = 0; j < 9;j++)
        {
            int index = (i/3)*3 + j/3;
            int num = board[i][j] - 0x30 -1;
            if(num >= 0 && num < 10)
            {
                list[index][num]++;
                col[i][num]++;
                row[j][num]++;
                if(list[index][num] > 1 || col[i][num] > 1 || row[j][num] > 1)
                    return false;
            }

        }
    }


    return true;
}
vector<bitset<9>> row;
vector<bitset<9>> col;
vector<bitset<9>> block;
vector<bitset<9>> possibilitys;

bitset<9> getPossibleStatus(int x, int y)
{
	int b = (x / 3) * 3 + y / 3;
	return ~(row[x] | col[y] | block[b]);
}



void possibilitylist()
{
	possibilitys.reserve(81);
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			possibilitys[i * 9 + j] = getPossibleStatus(i, j);
		}
	}
}

bool isValidSudoku1(int beg,vector<int>& find )
{
    int  b[9][9]= {};
    int  c[9][9] ={};
    int  r[9][9] ={};
    for(int i = 0;i < 9; i++)
    {
        for(int j = 0; j < 9;j++)
        {
            int index = (i/3)*3 + j/3;
            int num = find[i*9+j] - 1;
            if(num >= 0 && num < 10)
            {
                b[index][num]++;
                c[i][num]++;
                r[j][num]++;
                if(b[index][num] > 1 || c[i][num] > 1 || r[j][num] > 1)
                    return false;
            }
        }
    }
    return true;
}
void show(vector<int>& find)
{
	for (int i = 0; i < 81; i++)
	{
		if (i % 9 == 0)
			cout << endl;
		cout << find[i] << " ";
	}
	cout << endl;
}
bool getPossibility(vector<int>& find, int beg)
{
    if(!isValidSudoku1(beg,find))
        return false;
		
    for(int i = beg; i < 81;i++)
    {
        if(find[i] > 0 )
            continue;
		if(possibilitys[i].none())
			return false;
        for(int f = 0; f < 9;f++)
        {
            if(possibilitys[i].test(f))
            {
				int c = i % 9;
				int r = i / 9;
				vector<int> l;
				for (int ii = 0; ii < 9; ii++)
				{
					if (possibilitys[ii * 9 + c].test(f))
					{
						l.push_back(ii * 9 + c);
						possibilitys[ii * 9 + c].reset(f);
					}
				}
				for (int ii = 0; ii < 9; ii++)
				{
					if (possibilitys[r * 9 + ii].test(f))
					{
						l.push_back(r * 9 + ii);
						possibilitys[r * 9 + ii].reset(f);
					}
				}
				int b = (r / 3) * 3 + c / 3;
				for (int ii = 0; ii < 3; ii++)
				{
					for (int j = 0; j < 3; j++)
					{
						int index = ((b / 3) * 3 + ii) * 9 + (b % 3) * 3 + j;
						if (possibilitys[index].test(f))
						{
							l.push_back(index);
							possibilitys[index].reset(f);
						}
					}
				}
                find[i] = f+1;
                bool res =  getPossibility(find, i);
                if(res)
                    return true;
                find[i] = 0;
				for (auto v : l)
				{
					possibilitys[v].set(f);
				}
				
				cout << i << "\t" << f << "f" << endl;
            }
        }
		return false;
    }
    return true;
}
void Solution::solveSudoku(vector<vector<char>>& board)
{
    vector<int> find;
    find.reserve(81);
	row.reserve(9);
	col.reserve(9);
	block.reserve(9);
    for(int i = 0;i < 9; i++)
    {
        for(int j = 0; j < 9;j++)
        {
            int num = board[i][j] - 0x30 -1;
            if(num >= 0 && num < 10)
            {
                find[i*9 + j] = num+1;
				row[i] |= 1 << num;
				col[j] |= 1 << num;
				int b = (i / 3) * 3 + j / 3;
				block[b] |= 1 << num;
            }
        }
    }
	possibilitylist();
	bool ok = getPossibility(find,0 );
	if(ok)
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				if (board[i][j] == '.')
				{
					board[i][j] =	find[i * 9 + j]  + 0x30;
				}
			}
		}
	}
}
vector<int> countAnd(int n)
{
	vector<int> ret;
	if (n == 1)
	{
		ret.push_back(1);
		return ret;
	}
	auto res = countAnd(n - 1);
	int num = 1;
	int count = 0;
	for (auto v : res)
	{
		if (num == v)
			count++;
		else
		{
			if (count > 0)
			{
				ret.push_back(count);
				ret.push_back(num);
			}
			num = v;
			count = 1;
		}
	}
	ret.push_back(count);
	ret.push_back(num);
	return ret;
}
string Solution::countAndSay(int n)
{
	if (n < 1)
		return "";
	auto res = countAnd(n);
	string str;
	for (auto v : res)
	{
		str += to_string(v);
	}
	return str;
}

bool combination(vector<int>& candidates,int len, int target,vector<vector<int>>& ret)
{
    if(target == 0)
        return true;
    //使用动态规划
    bool result = false;
    for(int i = len-1; i >= 0;i--)
    {
        if(candidates[i] > target)
            continue;
        vector<vector<int>> tmp;
        bool ok = combination(candidates,i+1,target-candidates[i],tmp);
        if(ok)
        {
            result = true;
            if(tmp.empty())
            {
                vector<int> a;
                a.push_back(candidates[i]);
                ret.push_back(a);
            }
            for(auto t:tmp)
            {
                t.push_back(candidates[i]);
                ret.push_back(t);
            }
        }
    }
    return result;
}
vector<vector<int>> Solution::combinationSum(vector<int>& candidates, int target)
{
    if(candidates.empty())
        return {};
    sort(candidates.begin(),candidates.end());
    vector<vector<int>> ret;
    bool ok = combination(candidates,candidates.size(),target,ret);
    return ret;
}

vector<vector<int>> sret;
vector<int> path;

void dfs(vector<int>& candidates,int beg,int target)
{
    if(target == 0)
    {
        sret.push_back(path);    
        return;
    }
    for(int i = beg;i < candidates.size();i++)
    {
        if(candidates[i] > target)
            return;
        if(i > beg && candidates[i] == candidates[i-1])
            continue;
        path.push_back(candidates[i]);
        dfs(candidates,i+1,target-candidates[i]);
        path.pop_back();
    }
}


vector<vector<int>> Solution::combinationSum2(vector<int>& candidates, int target)
{
    if(candidates.empty())
        return {};
    sort(candidates.begin(),candidates.end());
    dfs(candidates,0,target);
    return sret;
}
int Solution::firstMissingPositive(vector<int>& nums)
{
    sort(nums.begin(),nums.end());
    int min = 1;
    for(auto v : nums)
    {
        if(v == min)
            min++;
    }
    return min;
}
//42. 接雨水
int Solution::trap(vector<int>& height)
{
    int sum = 0;
    int len = height.size();
    int l = 0;
    int r = l+2;
    int max = r;
    int num = 1;
    while( l < r&& r < len)
    {
        cout<<"len:"<<len<<"\tnum:"<<num++<<endl;
        if(l >= len)
            break;
        if(r >= len)
            break;


        if(height[l] == 0)
        {
            l++;
            r++;
            continue;
        }
        if(height[l] <= height[l+1])
        {
            l++;
            r++;
            continue;
        }
         if((height[r] > height[max] && r < len) || max <= l)
        {
            //寻找最大一个
            max = r;
        }
        if(height[r] >= height[l] || r == len-1)
        {
            int end = 0;
            if(r == len -1)
            {
                end = max;
            }
            else
            {
                end = r;
            }
            if(end < l+1)
                break;
            if(min(height[end],height[l]) == 0)
                break;
            int count = min(height[end],height[l]) * (end - l -1);
            for(int i = l+1;i< end;i++)
            {
                count -= min(height[i],height[end]);
            }
            cout<<"l="<<l<<"\tr="<<r<<"\tcount"<<count<<endl;
            sum += count;
            //结算
            l = end;
            r = l +2;
            max = r;
        }
        else
            r++;
    }
    return sum;
}
string Solution::multiply(string num1, string num2)
{
    if(num1=="0" || num2=="0")
        return "0";
    int l1 = num1.size() ;
    int l2 = num2.size() ;
    string res;
    vector<int> v;
    v.resize(l1+l2);
    for(int i = l1-1; i >= 0;i--)
    {
        for(int j = l2-1;j>= 0;j--)
        {
            int tmp = (num1[i] - '0') * (num2[j] -'0');
            int ten = tmp / 10;
            int once = tmp % 10;
            v[i+j+1] += once;
            v[i+j] += ten;
        }
    }
    for(int i = l1+l2-1;i>= 1;i--)
    {
        if(v[i] >= 10)
        {
            v[i-1] += v[i]/10;
        }
        v[i] =  v[i] % 10;
    }
    if(v[0] > 0)
        res.push_back('0' + v[0]);
    for(int i = 1;i < v.size();i++)
    {
        res.push_back('0' + v[i]);
    }
    return res;
}
bool Solution::isMatch(string s, string p)
{
    if(s.empty() && p.empty())
        return true;
    int i = 0;
    int j = 0;
    int iend = s.length() -1;
    int jend = p.length() -1;
    bool jump = false;
    int jumpIndex = -1;
    int index = -1;
    while(iend >= i && jend >= j)
    {
        if(p[jend] == '?')
        {
            iend--;
            jend--;
            continue;
        }
        if(p[jend] == '*')
            break;
        if(p[jend] != s[iend])
        {
            return false;
        }
        else
        {
            iend--;
            jend--;
        }
    }
    if(j > jend)
        return i > iend;
    while(i <= iend && j <= jend)
    {
        if(p[j] == '?' || s[i] == p[j])
        {
            i++;
            j++;
            continue;
        }
        if(p[j] == '*')
        {
            j++;
            jump = true;
            jumpIndex = j;
            index = i;
            continue;
        }
        if(s[i] != p[j] && jumpIndex != -1 && jumpIndex < jend)
        {
            index++;
            i = index;
            j = jumpIndex;
        }
        else
            return false;
    }
    while(j <= jend)
    {
        if(p[j] != '*')
            return false;
        j++;
    }
    return true;
}


